package day05;

import java.net.Inet4Address;
import java.util.Arrays;

public class MaoPao {
    public static void main(String[] args) {
        int[] arr = new int[10000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 10000000);
        }


        int[] arr2 = new int[]{10, 8, 11, 7, 4, 12, 9, 6, 5, 3};
        System.out.println(Arrays.toString(arr2));
        selectSort(arr2);
        /*
         * i=0 j=1  存储arr[1] 对比arr[1]和arr[0] 假设前面的大就把[0]的值赋给arr[1],
         *          放j为0退出,并且把arr[1]
         * */
    }

    //插入排序 之 直接插入排序  适用于基本排好的进行排序
    /*i =1 2   3   都不进行操作,前一个大于后一个 j=0 ,arr[1]=arr[0],把大的放到后面,
        i=3  j=2  arr[2]比arr[3]大,前面的大于后面的,执行内循环,把前面的大数存在后面,
        假定当前值arr[i]为最小值,与他前面的所有值进行比较,前面的值大于当前值,就挨个后移,交换位置,
        j--之后,到0那几个数据都没有比比这个数小不进行操作
    *   [5,10,2]
    扑克牌排序,在i前面的为插好的,i为当前拿的牌,当前牌与手中牌挨个比比较后,插入手中的扑克牌
    * */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i - 1;
            //拿到一张牌,如果比前面最大的那张大或者一样大,就直接放在牌的后面
            //如果比手中牌最后一个小,查找合适的位置插入,后面的挨个向右移
            int temp = arr[i];

            while (j >= 0 && temp < arr[j] ) {
                arr[j + 1] = arr[j];
                j--;
            }
            //j为前面最小那个数组所在位置,运算时候做了自减,这里加回来
            arr[j + 1] = temp;
            System.out.println(Arrays.toString(arr));
            // arr[j+1]=temp;//循环的时候j减少了1,所以这里加1,为

        }
        // System.out.println(Arrays.toString(arr));
    }

    //插入排序 之 希尔排序:先进行分组的插入排序,等到step为1的时候,不在分组,进行最后一次直接插入排序
    //做直接插入排序之前先分组式的插入排序,
    public static void shellSort(int[] arr, int n) {
        int i, j, temp, step;
        //分组
        for (step = n / 2; step > 0; step /= 2) {
            for (i = step; i < n; i++) {
                temp = arr[i];//拿出来放在外面腾出一个位置,不需要比对在放回去
                j = i - step;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];//大的向右移动,
                    j -= step;
                }
                arr[j + step] = temp;
                System.out.println("当前步长的值:" + step);
                System.out.println("当前temp的值:" + temp);
                System.out.println(Arrays.toString(arr));
            }
        }
    }

    //交换排序  之 快速排序（和插入排序的直接插入排序很像）
    public static void quickSort(int[] arr) {


        for (int i = 0, j = i; i < arr.length - 1; j = ++i) {
            int temp = arr[i + 1];
            while (temp < arr[j]) {
                arr[j + 1] = arr[j];
                if (j-- == 0) {
                    break;
                }
            }
            arr[j + 1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }

    //交换排序 之 选择排序(每次都选择一个最小的放在前面有序的位置)
    public static void selectSort(int[] arr) {

        for (int i = 0; i < arr.length-1; i++) {
            int min_index = i;//定义一个最小值的的下标,假设首个元素为最小,
            //第一轮,从数组中找到最小的插入到第一个位置
            //第二轮,从数组中找到最小的插入到第二个位置
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min_index] > arr[j]) {//从第2个元素开始,找到比当前下标元素还小的值,并且记录下标
                    min_index = j;
                }
            }
            if (min_index != i) {
                int temp = arr[i];
                arr[i] = arr[min_index];
                arr[min_index] = temp;
                System.out.println(Arrays.toString(arr));
            }
        }
        // System.out.println(Arrays.toString(arr));
    }

    //交换排序 之  冒泡排序
    public static void bubbleSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    //计数排序fh trt 规范化
    public static void countSort(int[] arr) {
        //输出最大值;
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i])
                max = arr[i];
        }
        //输出最小值
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (min > arr[i])
                min = arr[i];
        }
        //存放值的次数,而非值本身,下标才是值的本身
        int[] count = new int[max - min + 1];//定义一个最大值加1的长度数组,那么最后一个元素的下标值就等于最大值
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;//count数组的下标值就等于源数值的元素值.
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {//计数为0次代表,没有对应下标的数被计数
                //输出下标
                arr[index++] = i + min;
                System.out.print(i + "\t");
                count[i]--;//计数为多次的需要重复输出
            }
        }
        System.out.println();
        System.out.println(Arrays.toString(arr));
    }
    public static void bubbleSort_liecai(int[] arr){
        for (int j=arr.length-1;j>=0;j--){
            for (int i=0;i<j;i++) {
                if(arr[i]>arr[i+1]){
                    int temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
        }

    }
    //快速排序
    public static void quicksord(int[] arr){

    }

}




